Skip to main content

Full text of "mit :: lcs :: tm :: MIT-LCS-TM-032"

See other formats


mmmmmmmmmmm 



mmmmmmmm******* 



Mn7LCS/TM-32 



AN OPERATOR EMBEDDING THEOREM 

FOR COMPLEXITY CLASSES OF 

RECURSIVE FUNCTIONS 



Robert Mod 



May 1973 



MAC TECHNICAL MEMORANDUM 3 2 



AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES 
OF RECURSIVE FUNCTIONS 

Robert Moll 



May 1973 



This research was supported in part by the National Science 
Foundation under research grant GJ34671, and in part by the 
Advanced Research Projects Agency of the Department of 
Defense under ARPA Order No. 433 which was monitored by ONR 
Contract No. N00014-70-A-0362-0001. 



MASSACHUSETTS INSTITUTE OF TECHNOLOGY 
PROJECT MAC 



CAMBRIDGE MASSACHUSETTS 0213 9 



AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES 
OF RECURSIVE FUNCTIONS 

f 
Robert Moll 

Massachusetts Institute of Technology 

Spring 1973 

1. INTRODUCTION 

Let 3<(t) be the set of functions computable by some machine using 

no more than t(x) machine steps on all but finitely many arguments x. 

If we order the ^- classes under set inclusion as t varies over the 

recursive functions, then it is natural to ask how rich a structure 

is obtained. We show that this structure is very rich indeed. If R 

is any countable partial order and F is any total effective operator, 

then we show that there is a recursively enumerable sequence of 

recursive machine running times f$ ,,.} _ such that if iRk, then 

* s(k) J k€N 

^(F($ ,. N )) Q ^($ /,n), and if j and k are incomparable, then F(§ ..,) < 

~ s(j) ? s(k;r' J y ~ v s (jr 

$ ., . on infinitely many arguments, and F(§ ., . ) < $ ... on infinitely 
s(k) J ~ s(k) s(j) 

many arguments. 

An interesting feature of our proof is that we avoid appealing 
explicitly to the continuity of total effective operators; indeed our 
proof follows directly from a single appeal to the recursion theorem. 

Several investigators have considered this and related problems, and 
in Section 4 we briefly summarize these investigations and compare them 
to our own. 



-2- 



2. PRELIMINARIES 

For notation from recursive function theory we follow Rogers [2 ]. 

For each n € N, P^ stands for the partial recursive functions of 
n-variables, and » n stands for the total recursive functions of n 
variables. 

We use (a.e.) to denote "almost everywhere", which for our 
purposes stands for "all but finitely many". Similarly (i.o.) stands 
for "infinitely often". 

Suppose {cDq.CPj^,...} is a Godel numbering of P . A measure on 
Computation [1] $ = {$ Q ,§ 1 ,...) is a sequence of functions in P 
satisfying 

1. Vi € N [dom(co.) = dom($.)] 

2. \ixy[§ (x) = y] is a recursive predicate. 

If we think of our Godel numbering in the usual one-tape Turing machine 
formalism, then 

$ i (x) = "the number of steps in the computation of the i th Turing 
machine on argument x" is a measure on computation. 

Henceforth let $ be some fixed measure on computation. Then we 
define for any total function t 

F(t) = [i e. N f 00. € ^, and $ s t (a.e.)}, 
1 i 

and 

y(t) = {CD. I i e F(t)}. 



■3- 



That is, F(t) is the set of (indices of ) total machines which run 
in time t, and 5?(t) is the set of total functions computable within 
time t. ^(t) is called a complexity class . 

A sequence of partial functions f = {\|j ,41.. , . . .] is said to be 
an r.e. sequence of partial functions if \ix[i|j . (x) ] € P_. 



1 



V 



The following theorem of Blum [ 1 ] shows that we can uniformly 
enlarge complexity classes ^(t) if t is a sufficiently well-behaved 
function. 

Theorem . (Compression Theorem) There is a g f fl such that for every 
§. € ft.., ^(f.)5 y(\xg(x,$ . (x)) . g is called a compression function 
for $ . 

An operator is a map which takes functions to functions; we 

write F(f)(x) to mean the value of the operator F applied to the 

function f, evaluated at x. An operator F: D £ P.. -* P is called an 

effective operator if there is an s € ft, such that F(© ) (x) = CD , •. (x) . 
— c 1 ~ e s(e; 

An effective operator F is total effective if for every f € ft,, 
F(f) is defined and F(f) f ft . 

3 . THE EMBEDDING THEOREM 

Theorem . Let F be any total effective operator, and let R be any recursive 

countable partial order on N. Then there exists an r.e. sequence of 

recursive functions p,.., p.. , . . . p ... such that if jRk, then F(p ) < 

u I n ~ j 

p, (a.e.), and if j and k are incomparable, then F(p.) < p. (i.o.), and 

k ~ j K 

p < F(p.) (i.o.). 
K ~ J 



Proof. We assume without loss of generality that R orders N-{0} 
rather than N, and in addition that R contains kRO for each k > 0. 

Let d = < i 0' k >J a l = < l V k l > » ••• 'a n = < i n , k n >, ... be a 
recursive listing of all incomparable pairs in R such that if x and 
y are incomparable, then < x, y > and < y x > both appear infinitely 
often in the list. As a technical convience we define max[c5] = 0. 
Let s € fc 2 be the Sl function of the s-m-n theorem defined by the 
equation 



<*>-(< x ', y >) = © , ,(y) 
e ' s(e,x) w/ 



Define i|/ £ P as follows: 



if x < k or 3n < k such that $ (< 0, n >) > x, (1) 



g U s(e )j )« + ^ s(e , j ))«]) + 
jRk 



fo s(e,i)« + ^s(e,i )>WJ. 



(2)(i) 



(2) (ii) 



t(e, <k,x >) = 



where n = \m <: x[((m = 0) and (x = k )) or 

[(m > 0) and (k = k ) and [(Vi ( <; i <: m) ) 

(3z ± s: x) such that (z = k ) and 

(Z i+l = 2 i + § s(e,k.) (2 i)) 2=d (^^x)]]], if 
such an n exists and (1) is not true, and 



HIS* b r n (x) + F(oo .v)(x)] otherwise 

iRk 



(3) 



£ P since all the test computations in clauses (1) and (2) are 



recursive by the second measure on computation axiom. By the recursion 

theorem there is an e such that i|r(e, <k,x >) = cp (<k,x>); we apply the 

s-1-1 version of the s-m-n theorem to obtain i|f(e, <k,x>) = CD / , ,. (x) • 

s (,e, K) 

To simplify our notation we now suppress mention of e and write p, (x) = 



cp 



s(e,k) 
now becomes 



(x) . Similarly we write § (x) for $ 



s(e,k) 



(x) . Our definition 



»k« = 



r • 



< 



if x < k or 3n < k such that $ (n) < x, 
— P 



+ 



(1) 

(2)(D 
(2)(ii) 



max[ p .(x) + F(p.)(x)]) 

jRk [P., (x) + F(p. )(x)], 

n n 

where n = um ^ x[((m = 0) and (x s k )) or 

[(m > 0) and (k = k ) and [(Vi(0 <; i <: m))(3z. <: x) 
m l 

such that (z_ = k.) and (z. ... = z. + § (z )) and 
U U 1+1 1 Pi 1 

i 

(z = x) ] ] ] , if such an n exists and (1) is not 

m 

true, and 



max [n . (x) +F(n.)(x)] otherwise. 

i ~ i 

]<X J J 

jRk 

We first establish that at most finitely many of the functions 

fa,} ,- can be non-total. Suppose p, (x) diverges. Since p is defined 
r k k€N k u 

by (3) at all arguments, P Q (x) must diverge, and so by (1) p (x) = 
for all j > x. 



(3) 



-6- 



We now prove that for all k p is total. 



Say that a n is serviced at x if Pfc ( x ) is defined by (2), and if 

n 
n is the least m =£ x satisfying the body of (2) in the definition of 

P k (x). We allow the possibility that P (x) may diverge. If a is 

n ti n _i 

servxced at x, (2) guarantees that x = z = £ z + $ (z ) and so 

n i=l i P k. i ' 

a n is serviced at no other argument. Moreover, if a is serviced at x 

n 

and p k (x) diverges, then for n' > n a, will never be serviced, since 
n n 

a^, is serviced at y only when y bounds the computation of $, (x) . 



P k 



Let k be an R-minimal element in the finite set (k* I p , non-total] 

1 k J 

Then if p k (x) diverges, it must do so because of (2) (ii) . That is a 

' n 

is serviced at x for some n, and p. must be non- total. 

n 

But suppose p. (y) diverges by an instance of (2) (ii) for some y. 
n 
This means that i^ = k for some j and a. is serviced at y. If j < n, 

then y must equal z but since a is serviced x, $ (z ) < x and hence 

J n P k. J 

J 

P (z ) must converge. If j > n , then since a is serviced at x and 
j J n 

P k (x) is assumed to diverge, a. is never serviced. Moreover i cannot 

J 

equal n, for then i would equal k . Hence p. must be non- total because 

n n l 

n 

of (2)(i) or (3), and so some function p., such that i'Ri is non-total. 

1 n 



Let i be R minimal among fi' | i'R i and i' non-total} . Then 



n 

p. must be non-total by an instance of (2)(ii), say at argument y. 

j-l 
Hence i = k. for some j, and a. must be serviced at y = L z^ + 

2 J 151=0 

§ (z ). If j < n, p. (y) must converge since a is serviced at x 
Pi m r K. n 

k J 

by assumption; and if j = n, then i and k are comparable, a contra- 

n n 

diction. Furthermore if i > n. then a. will never be serviced. Hence 

J 

p. is total, and we conclude that for every k p, € &,. 
1 *k 1 

If jRk, then F(p.)(z) ^ p, (z) for all z > m n ='max[k,i,$ (0), 
~ J ^k — Pq 

* (1), ... $ (k-1)]. 

p o Po 

If j and k are incomparable, then < i,k > = a. , a , ... a , ... 

1 q 

for some infinite sequence n_ < n, < n„ • • • n ••• . 

12 q 

For arguments z > m_ p, (z) is defined by (2) or (3). Since the 

sequence of z.'s is strictly increasing, there is an i n such that for 

i > i- > z - ^ m n- At those arguments z. for i > i , i = n , p (z.) will 

be defined by clause (2) and p,(z.) > F(p.)(z.). A symmetric argument 

k 1 j 1 

shows that p. > F(p_ ) (i.o. ) , and the theorem is proved. 
J k 

Corollary . Let F be any total effective operator, and let R be any 

countable partial order on N. Then there exists an r.e. sequence of 

recursive measure functions $ ... , § ,.., ... such that if jRk, then 

r(0) r (1) 

F(§ ..,) < § ,. , (a.e.) and 3?(F($ ,.Jc ?(§ ..,), and if j and k are 
~ r(jX r(k) v ~ v r(j;r? r(k) y ' 

incomparable, then F($ ...) <$ ...(i.o.), and F($ ., . ) <§ ...(i.o.). 

r(j) r(k) v ~ r(k) r(j) v 



-8- 



Proof . Mostowski [ 3 ] has shown that there is a countable partial 
order R into which any countable partial order may be embedded. 
Moreover, Sacks [4] has shown that r" is recursive. 

We assume without loss of generality that F is at least as large 
as the identity operator, and that the compression function for $, g, 
is strictly increasing in its second argument. Blum [ 1 ] has shown 
that there is an h € ^ 2 such that for all i cp.(x) < h(x, § . (x)) (a. e. ) . We 
assume that h is strictly increasing in its second argument. To prove 
the corollary, apply the theorem to r'', rewrite clause (2) as 



max [p (x>h(x,g(x,F($ )(x)))] + [ p . ( x ) + h(x,g(x,F($ )(x)))], 
J*X J ~ Pj L n ~ Pi 

iRk n 

and we rewrite clause (3) as 



max[p.(x) + h(x,g(x,F($ )(x)))] 

jRk 



j*x J ~ Pj 



It is easy to see that the theorem goes through as before, and the 

monotonicity restrictions on g and h guarantee that the functions 

{$ } k g N satisfy the corollary, 
k 



4 . RELATION TO OTHER WORK, AND OPEN PROBLEMS 

McCreight [5] is the first investigator to prove an embedding 
theorem for subrecursive classes. He shows that any countable partial 
order can be embedded in the complexity classes ordered under set 
inclusion. However, his theorem is weaker than our results in that 
the functions of his partial order are "separated" by composition 
with a fixed recursive function, whereas our functions are separated 
by a total effective operator. In [6] Enderton also proves a universal 
embedding theorem for subrecursive classes. His notion of a sub- 
recursive class is quite weak, however, and his result is an immediate 
corollary of McCreight 's theorem. 

Early work on the structure of subrecursive classes was done by 
Feferman [12], Meyer and Ritchie [7], and Basu [8]. Feferman shows 
that dense chains exist for various notions of subrecursive classes. 
Meyer and Ritchie define what they call elementary honest classes, and 
they show the existence of dense chains and infinite anti-chains for 
such classes. Moreover, they are able to exhibit certain functions f 
such that dense chains of classes will exist between f and the iterate 
of f, \x[f (x)]. Basu builds dense chains of subrecursive classes, where 
these classes are closed under the application of a fixed recursive operator. 

Machtey [11] has announced universal embedding theorems for both 
the "honest" primitive recursive degrees and the "dishonest" primitive 
recursive degrees. Both of these theorems follow immediately from our 
results. 



W^ •'5**»!tW«I 



ji.j.m uv r 4«WilHWWWWai 



-10- 



We also note that Alton [ 9 ^hM^^penfeptiL*.; announced our 
embedding theorem. 

We leave open the question of the size of the functions In our 
embedding theorem. That is, given F, what is a reasonable upper bound 
on the sise of p Q in terms of F(recall that "^ bounds all the functions 
(P k ) keN on all arguments). * 

The author wishes to acknowledge the generous assistance of Professor 
Albert R. Meyer in the conception and preparation of this paper. 



-11- 



REFERENCES 



1. M. Blum, A machine- independent theory of the complexity of 
recursive functions, JACM 14 , 1967, 322-336. 

2. H. Rogers, Jr., Theory of recursive functions and effective 
computability, McGraw-Hill, 1967. 

it 

3. A. Mostowski, Uber gewisse universelle relationen, Ann . Soc . 
Polon . Math. 17, 1938, 117-118. 

A. G. Sacks, Degrees of unsolvability, Annuals of Math . Studies , 
No. 55, Princeton, N.J. 1963. 

5. E. McCreight, Classes of computable functions defined by bounds 
on computation, Doctoral Dissertation, Carnegie-Mellon University, 
Department of Computer Science, 1969. 

6. H. Enderton, Degrees of computational complexity, JCSS No . 6, 
1972, 389-396. 

7. A. Meyer and D. Ritchie, Classification of functions by compu- 
tational complexity, Proc . of the Hawaii Internat' 1 Conf . on Sys . 
Sciences , 1968, 17-19. 

8. S.K. Basu, On classes of computable functions, ACM Symp . on Theory 
of Computing , 1969, 55-61. 

9. D. Alton, Operator embeddability in computational complexity, 
Notices of the AMS, 1972, A-763. 

10. A. Meyer and P. Fischer, Computational speed-up by effective operators, 
JSL, No. 37, 1972, 55-68. 

11. M. Machtey, Augmented loop languages and classes of computable 
functions, JCSS , to appear. 

12. S. Feferman, Classifications of recursive functions by means of 
hierarchies, Trans , of the AMS, No. JL04, 1962, 101-122. 



UNCLASSIFIED 



Security Classification 



DOCUMENT CONTROL DATA -R&D 

(Security classification of title, body of abstract and indexing annotation must be entered when the overall report is classified) 



i. originating ACTIVITY (Corporate author) 

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 
PROJECT MAC 



2a. REPORT SECURITY CLASSIFICATION 



UNCLASSIFIED 



2b. GROUP 

NONE 



3 REPORT TITLE 



AN OPERATOR EMBEDDING THEOREM FOR COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS 



4. descriptive NOTES (Type of report and inclusive dates) 

INTERIM SCIENTIFIC REPORT 



5 authORIS) (First name, middle initial, last name) 



ROBERT MOLL 



6. REPORT DATE 

M&Y 17, 1973 



7a. TOTAL NO. OF PAGES 



11 



lb. NO. OF REFS 



12 



3a. CONTRACT OR GRANT NO. 



9a, ORIGINATOR'S REPORT NUMBER(S) 



N00014-70-A-036 2-0006 



fa. PROJ EC T NO. 



MAC TM-32 



9b. OTHER REPORT NO(S) (Any other numbers that may be assigned 
this report) 

NONE 



10. DISTRIBUTION STATEMENT 



DISTRIBUTION OF THIS DOCUMENT IS UNLIMITED 



11 SUPPLEMENTARY NOTES 



12. SPONSORING MILITARY ACTIVITY 



OFFICE OF NAVAL RESEARCH 



13. ABSTRAC T 



Let ^(t) be the set of functions computable by some machine 
within time bound t(x) for all but finitely many arguments. If 
F is any total effective operator and R is any recursive countable 
partial order, then there is an r.e. sequence of recursive machine 
running times T , T^ . . . , T , ... such that if iRj then 3 J (F(T i >) C". 
S?(T.), and if i and j are incomparable, then F( T i ) < T .= (i»°«)» 

J *J 

and F(T.) < T. (i.o.). 



DD, f n o r v m 65 1473 < PAGE " 



UNCLASSIFIED 



S/N 0102-014- 6600 



Security Classification 



UNCLASSIFIED 



Security Classification 



KEY WO RDS 



recursive partial order 

complexity class 

total effective operator 



DD , F N °o R vM473 back) 

(PAGE 2) 



UNCLASSIFIED 



Security Classification